package pocisk;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * Implementacja algorytmu Nealdera-Meada
 *
 * @author kamil
 */
public class NelderMead {

    // nic nie mówiące współczynniki, tak w książke pisało
    private double q = 1;
    private double X = 2;
    private double Y = 0.5;
    private double S = 0.5;

    /**
     * Metoda liczy najlepsze wartości kryterium dla danych zmiennych decyzyjnych
     *
     * @param simplex   zbiór poczatkowych wartości, od których ma zacząć poszukiwanie.
     * Jeśli operujemy na N zmiennych decyzyjnych, to zbiór simplex ma mieć N+1 elementów.
     * @param fun       funkcja celu
     * @param t       ograniczenie dokładności obliczeń
     * @param kmax            ograniczenie ilości iteracji
     *
     */
    public double[] nelderMead(ArrayList<Double[]> simplex, HitTargetFunction fun, double t, int kmax) {
        int Np1 = simplex.size() - 1;
        int N = simplex.size() - 2;

        //licz wartości funkcji celu
        ArrayList<Double> funSimplex = evaluateFunction(fun, simplex);

        //sortuj zbior simpleksów względem wartości funkcji celu
        ArrayList<Double[]> orderedSimplex = sortSimplex(simplex, funSimplex); // potem można zastąpić simplex


        while (kmax > 0) {
            funSimplex = evaluateFunction(fun, orderedSimplex);
            orderedSimplex = sortSimplex(orderedSimplex, funSimplex);
            //printSimplex(orderedSimplex, fun);

            kmax--;
            if (fun.function(toSmallDouble(orderedSimplex.get(Np1))) - fun.function(toSmallDouble(orderedSimplex.get(0))) <= t) {
                break;
            }

            double[] worst = toSmallDouble(orderedSimplex.get(Np1));     // najgorszy punkt
            double[] convexHull = convexHull(orderedSimplex);            //wyznacz otoczke
            double[] xr = xr(convexHull, worst);
            double fr = fun.function(xr);
            double fx1 = fun.function(toSmallDouble(orderedSimplex.get(0)));
            double fxN = fun.function(toSmallDouble(orderedSimplex.get(N)));
            double fxNp1 = fun.function(toSmallDouble(orderedSimplex.get(Np1)));

            if (fx1 <= fr && fr < fxN) {
                orderedSimplex.set(Np1, toBigDouble(xr));
                continue;
            } else if (fr < fx1) {
                double[] xe = xe(convexHull, worst);
                double fe = fun.function(xe);
                if (fe < fr) {
                    orderedSimplex.set(Np1, toBigDouble(xe));
                    continue;
                } else {
                    orderedSimplex.set(Np1, toBigDouble(xr));
                    continue;
                }
            }
            if (fr >= fxN) {
                if (fxN <= fr && fr < fxNp1) {
                    double[] xc = xc(convexHull, worst);
                    double fc = fun.function(xc);
                    if (fc <= fr) {
                        orderedSimplex.set(Np1, toBigDouble(xc));
                        continue;
                    } else {
                        orderedSimplex = shrink(orderedSimplex);
                        continue;
                    }
                } else if (fr >= fxNp1) {
                    double[] xcc = xcc(convexHull, worst);
                    double fcc = fun.function(xcc);
                    if (fcc < fxNp1) {
                        orderedSimplex.set(Np1, toBigDouble(xcc));
                        continue;
                    } else {
                        orderedSimplex = shrink(orderedSimplex);
                        continue;
                    }
                }
            }
        }
        return toSmallDouble(orderedSimplex.get(0));

    }

    private static double[] toSmallDouble(Double[] d) {
        double[] result = new double[d.length];
        for (int i = 0; i < d.length; i++) {
            result[i] = d[i];
        }
        return result;
    }

    private Double[] toBigDouble(double[] d) {
        Double[] result = new Double[d.length];
        for (int i = 0; i < d.length; i++) {
            result[i] = d[i];
        }
        return result;
    }

    private double[] convexHull(ArrayList<Double[]> simplex) {
        int dim = simplex.get(0).length;
        double[] simplexSum = new double[dim];
        for (int i = 0; i < simplex.size() - 1; i++) {
            for (int j = 0; j < simplexSum.length; j++) {
                simplexSum[j] += simplex.get(i)[j];
            }
        }
        double[] result = new double[dim];
        for (int d = 0; d < dim; d++) {
            result[d] = simplexSum[d] / (simplex.size() - 1);
        }
        return result;

        //double[] convexHull = new double[]{1d / simplex.size() * simplexSum0, 1d / simplex.size() * simplexSum1};
    }

    private void printSimplex(ArrayList<Double[]> simplex, HitTargetFunction fun) {
        String s = "Simplex {";
        for (Double[] el : simplex) {
            s += "[";
            for (Double d : el) {
                s += d + ", ";
            }
            s = s.substring(0, s.length() - 2);
            s += "]:" + fun.function(toSmallDouble(el)) + ", ";
        }
        s = s.substring(0, s.length() - 3);

        s += "}";
        System.out.println(s);
    }

    private double[] xr(double[] conv, double[] worst) {
        double[] result = new double[conv.length];
        for (int i = 0; i < conv.length; i++) {
            result[i] = (1 + q) * conv[i] - q * worst[i];
        }
        return result;
    }

    private double[] xe(double[] conv, double[] worst) {
        double[] result = new double[conv.length];
        for (int i = 0; i < conv.length; i++) {
            result[i] = (1 + q * X) * conv[i] - q * X * worst[i];
        }
        return result;
    }

    private double[] xc(double[] conv, double[] worst) {
        double[] result = new double[conv.length];
        for (int i = 0; i < conv.length; i++) {
            result[i] = (1 + q * Y) * conv[i] - q * Y * worst[i];
        }
        return result;
    }

    private double[] xcc(double[] conv, double[] worst) {
        double[] result = new double[conv.length];
        for (int i = 0; i < conv.length; i++) {
            result[i] = (1 + Y) * conv[i] - Y * worst[i];
        }
        return result;
    }

    private ArrayList<Double> evaluateFunction(HitTargetFunction fun, ArrayList<Double[]> simplex) {
        ArrayList<Double> funSimplex = new ArrayList<Double>();
        for (Double[] p : simplex) {
            funSimplex.add(fun.function(toSmallDouble(p)));
        }
        return funSimplex;
    }

    private ArrayList<Double[]> shrink(ArrayList<Double[]> orderedSimplex) {
        double[] best = toSmallDouble(orderedSimplex.get(0));
        ArrayList<Double[]> result = new ArrayList<Double[]>();
        result.add(orderedSimplex.get(0));
        for (int i = 1; i < orderedSimplex.size(); i++) {
            Double[] elem = new Double[orderedSimplex.get(0).length];
            for (int j = 0; j < orderedSimplex.get(i).length; j++) {
                elem[j] = best[j] + S * (orderedSimplex.get(i)[j] - best[j]);
            }
            result.add(elem);
        }
        return result;
    }

    private ArrayList<Double[]> sortSimplex(ArrayList<Double[]> sim, ArrayList<Double> fun) {
        Map<Double[], Double> map = new HashMap<Double[], Double>();
        for (int i = 0; i < sim.size(); i++) {
            map.put(sim.get(i), fun.get(i));        // simpleksy muszą być unikatowe!!!!
        }

        Map resultMap = sortByValue(map);
        return new ArrayList<Double[]>(resultMap.keySet());

    }

    private Map sortByValue(Map map) {
        List list = new LinkedList(map.entrySet());
        Collections.sort(list, new Comparator() {

            public int compare(Object o1, Object o2) {
                return ((Comparable) ((Map.Entry) (o1)).getValue()).compareTo(((Map.Entry) (o2)).getValue());
            }
        });

        Map result = new LinkedHashMap();
        for (Iterator it = list.iterator(); it.hasNext();) {
            Map.Entry entry = (Map.Entry) it.next();
            result.put(entry.getKey(), entry.getValue());
        }
        return result;
    }
}
